home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_04 / ross / bldtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-09  |  1.7 KB  |  84 lines
  1. Figure 2
  2. --------
  3.  
  4. A program that reads a file and generates a Huffman encoding tree
  5. based on the character frequencies in that file.
  6.  
  7.  
  8. /* --------------------------- bldtree - main ----------------------------- */
  9.  
  10. #include <stdio.h>
  11. #define MAIN
  12. #include "hufftree.h"
  13.  
  14. long htcnt[512];
  15.  
  16. main(int argc, char *argv[])
  17. {
  18.   FILE *fin, *fout;
  19.   int c;
  20.   int i;
  21.   int ntree = 256;
  22.   short h1, h2;
  23.  
  24.   if (argc < 2)
  25.   { fprintf(stderr,"usage: %s infile \n",argv[0]);
  26.     exit(0);
  27.   }
  28.  
  29.   if ((fin = fopen(argv[1],"rb")) == NULL)
  30.   { fprintf(stderr,"Unable to open %s for input\n",argv[1]);
  31.     exit(1);
  32.   }
  33.  
  34.   if ((fout = fopen("htree.dat","wb")) == NULL)
  35.   { fprintf(stderr,"Unable to open htree.dat for output\n");
  36.     exit(1);
  37.   }
  38.  
  39.   /* initialize character counts so all characters recognized */
  40.   for (i=0; i<256; i++)
  41.     htcnt[i] = 1;
  42.  
  43.   /* count character occurrence frequencies */
  44.   while ((c = fgetc(fin)) != EOF)
  45.   { htcnt[c]++;
  46.   }
  47.  
  48.   /* build Huffman tree */
  49.   while(1)
  50.   { h1 = 0;
  51.     h2 = 0;
  52.     for (i=0; i<ntree; i++)
  53.     { if (i != h1)
  54.       { if (htcnt[i] > 0 && ht[i].parent == 0)
  55.         { if (h1 == 0 || htcnt[i] < htcnt[h1])
  56.           { if (h2 == 0 || htcnt[h1] < htcnt[h2])
  57.               h2 = h1;
  58.             h1 = i;
  59.           }
  60.           else if (h2 == 0 || htcnt[i] < htcnt[h2])
  61.             h2 = i;
  62.         }
  63.       }
  64.     }
  65.     if (h2 == 0)
  66.     { root = h1;
  67.       break;
  68.     }
  69.     ht[h1].parent = ntree;
  70.     ht[h2].parent = ntree;
  71.     htcnt[ntree] = htcnt[h1] + htcnt[h2];
  72.     ht[ntree].right = h1;
  73.     ht[ntree].left = h2;
  74.     ntree++;
  75.   }
  76.  
  77.   /* write out tree */
  78.   fwrite(&root, sizeof(root), 1, fout);
  79.   fwrite(ht, sizeof(ht), 1, fout);
  80.   fclose(fin);
  81.   fclose(fout);
  82. }
  83.  
  84.